package com.mango.leet.code.week1.game286;

/**
 * 5236. 美化数组的最少删除数
 */
/**
 * 给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
 *
 * nums.length 为偶数
 * 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
 * 注意，空数组同样认为是美丽数组。
 *
 * 你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
 *
 * 返回使 nums 变为美丽数组所需删除的 最少 元素数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2,3,5]
 * 输出：1
 * 解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
 * 示例 2：
 *
 * 输入：nums = [1,1,2,2,3,3]
 * 输出：2
 * 解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 0 <= nums[i] <= 105
 */

/**
 * @Author: mango
 * @Date: 2022/3/27 5:22 下午
 */
public class LC5236 {
    class Solution {
        public int minDeletion(int[] nums) {
            //return process(nums,0,nums.length);
            return handle(nums);
        }
        // 指针法，可以用栈记录最后数组，不过题目没有要求，所以不用体现栈
        public int handle(int[] nums){
            // 记录要删除的数
            int result = 0;
            for(int i=0;i<nums.length;i++){
                // 如果下标满足新数组的偶数下标
                if((i-result)%2==0){
                    // 最右一位偶数下标，且右边没有数和它比较，直接删除，result++
                    if(i+1==nums.length){
                        result++;
                        break;
                    }
                    // 偶数下标，且与后一位相等，则直接删除
                    if(nums[i] == nums[i+1]){
                        result++;
                    }
                }
            }
            return result;
        }

        /**
         * 递归法
         * @param nums 原数组
         * @param l 起点下标，左
         * @param r 结束下标，右
         * @return 需要删除的个数
         */
        public int process(int[] nums,int l,int r){
            // 个数
            int result = 0;
            // 定义下标-1，如果没找到则为-1，说明已经是漂亮数组了
            int index = -1;
            // 开始遍历，i = i + 2
            for(int i=l;i<r;i=i+2){
                // 如果i是最右一位，则没有后一位和它不相等，result直接加1后退出循环
                if(i+1 == r){
                    result++;
                    break;
                }
                // 如果i和后一位相等，记录当前下标，result++,退出循环
                if(nums[i] == nums[i + 1]){
                    index = i;
                    result++;
                    break;
                }
            }
            // 递归退出条件，如果没有找到需要处理的数，则说明已经是漂亮数组了，则退出
            if(index == -1){
                return result;
            }
            // 找到了不满足的下标index，递归处理下一个位置开始的数组
            result += process(nums,index+1,r);
            return result;
        }
    }
}
